package leetcode.binaryTree;

import datastructure.tree.TreeNode;

/**
 * @Description: https://leetcode.cn/problems/recover-binary-search-tree/
 * @Author Ammar
 * @Create 2023/7/16 20:27
 */
public class _99_恢复二叉搜索树 {
    private TreeNode<Integer> first;
    private TreeNode<Integer> second;
    private TreeNode<Integer> prev;

    public void recoverTree(TreeNode<Integer> root) {
        inorder(root);
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }

    private void inorder(TreeNode<Integer> root) {
        if (root == null) return;
        inorder(root.left);
        if (prev != null && prev.val > root.val) {
            second = root;
            if (first != null) return;
            first = prev;
        }
        prev = root;
        inorder(root.right);
    }

    private void find(TreeNode<Integer> node) {
        if (prev != null && prev.val > node.val) {
            second = node;
            if (first != null) return;
            first = prev;
        }
        prev = node;
    }

    public void recoverTree1(TreeNode<Integer> root) {
        TreeNode node = root;
        while (node != null) {
            if (node.left != null) {
                TreeNode pred = node.left;
                while (pred.right != null && pred.right != node) {
                    pred = pred.right;
                }
                if (pred.right == null) {
                    pred.right = node;
                    node = node.left;
                } else {
                    find(node);
                    // 第二次遍历到该节点
                    pred.right = null;
                    node = node.right;
                }
            } else {
                find(node);
                node = node.right;
            }
        }
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
}
